//class Solution {
//    public String reversePrefix(String word, char ch) {
//        char[] words=word.toCharArray();
//        for(int i=0;i<words.length;i++){
//            if(words[i]==ch){
//                int l=0;
//                int r=i;
//                while(l<r){
//                    char c=words[l];
//                    words[l]=words[r];
//                    words[r]=c;
//                    l++;
//                    r--;
//                }
//                break;
//            }
//        }
//        return new String(words);
//    }
//}







//
//class Solution {
//    public int countOdds(int low, int high) {
//        if(low%2==1||high%2==1){
//            return (high-low)/2+1;
//        }
//        return (high-low)/2;
//    }
//}








//class Solution {
//    public int findPeakElement(int[] nums) {
//        int l=0;
//        int r=nums.length-1;
//        while(l<r){
//            int mid=l+((r-l)/2);
//            if(nums[mid]<nums[mid+1]){
//                l=mid+1;
//            }else{
//                r=mid;
//            }
//        }
//        return l;
//    }
//}









//class Solution {
//    public int expectNumber(int[] scores) {
//        HashSet<Integer> hash=new HashSet<Integer>();
//        for(int x : scores){
//            hash.add(x);
//        }
//        return hash.size();
//    }
//}










//class Solution {
//    public int breakfastNumber(int[] staple, int[] drinks, int x) {
//        Arrays.sort(staple);
//        Arrays.sort(drinks);
//        int lens=staple.length;
//        int lend=drinks.length;
//        int i=0;
//        int j=lend-1;
//        int sum=0;
//        while(i<lens&&j>=0){
//            if(staple[i]+drinks[j]<=x){
//                sum=(sum+j+1)%1000000007;
//                i++;
//            }else{
//                j--;
//            }
//        }
//        return sum%1000000007;
//    }
//}










//class Solution {
//    public int paintingPlan(int n, int k) {
//        if(0==k||n*n==k){
//            return 1;
//        }
//        else if(k<n){
//            return 0;
//        }
//        else{
//            int sum=0;
//            for(int i=0;i<=n;i++){
//                for(int j=0;j<=n;j++){
//                    if(((i*n)+(j*n)-(i*j))==k){
//                    sum+=painting(n,i)*painting(n,j);
//                    }
//                }
//            }
//            return sum;
//        }
//    }
//    public int painting(int a,int b){
//        int num1=1;
//        int num2=1;
//        while(b>0){
//            num1*=a;
//            a--;
//            num2*=b;
//            b--;
//        }
//        return num1/num2;
//    }
//}











//class Solution {
//    public String dayOfTheWeek(int day, int month, int year) {
//        String[] str=new String[]{"Sunday","Monday","Tuesday","Wednesday","Thursday","Friday","Saturday"};
//        int sum=4;
//        int[] months=new int[]{31,28,31,30,31,30,31,31,30,31,30,31};
//        if(year>1971){
//            for(int i=1971;i<year;i++){
//                sum+=365;
//                if(i%4==0&&i%100!=0||i%400==0){
//                    sum+=1;
//                }
//            }
//        }
//        for(int i=0;i<month-1;i++){
//            sum+=months[i];
//        }
//        if(month>=3&&(year%4==0&&year%100!=0||year%400==0)){
//            sum++;
//        }
//        sum+=day;
//        return str[sum%7];
//    }
//}













//class Solution {
//    public int[][] allCellsDistOrder(int rows, int cols, int rCenter, int cCenter) {
//        int[][] arr=new int[rows*cols][];
//        for(int i=0;i<rows;i++){
//            for(int j=0;j<cols;j++){
//                arr[i*cols+j]=new int[]{i,j};
//            }
//        }
//        Arrays.sort(arr,new Comparator<int[]>(){
//            public int compare(int[] a,int[] b){
//                return (Math.abs(a[0]-rCenter)+Math.abs(a[1]-cCenter))-(Math.abs(b[0]-rCenter)+Math.abs(b[1]-cCenter));
//            }
//        });
//        return arr;
//    }
//}
